package pers.zc.activiti.workflow;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * @Annotion: 无环图所有路径
 * @ClassName: TwoPointsPath
 * @Author: Lin Fuyuan
 * @Date: 2019/9/29  9:54
 * @Version: 1.0
 */
public class PointsPath {
    /**
     * 当前路径
     */
    private static List<Long> nowPath = new ArrayList<>();
    /**
     * 所有环
     */
    private Set<List<Long>> cycleList = new HashSet<>();
    /**
     * 所有可达路径
     */
    private Set<List<Long>> pathList = new HashSet<>();

    /**
     * 指定一个初始节点和一个终点
     *
     * @param nodes
     * @param startPoint
     * @param endPoint
     */
    public PointsPath(List<Node> nodes, Long startPoint, Long endPoint) {
        this.findAllPath(nodes, startPoint, endPoint);
    }

    /**
     * 只指出初始节点
     *
     * @param nodes
     * @param startPoint
     */
    public PointsPath(List<Node> nodes, Long startPoint) {
        /*找出所有的终止节点*/
        List<Long> endPoints = getEndPoints(nodes);
        for (Long endPoint : endPoints) {
            findAllPath(nodes, startPoint, endPoint);
        }
    }

    /**
     * 只给出原始节点关系,返回所有可能路径
     *
     * @param nodes
     */
    public PointsPath(List<Node> nodes) {
        /*找出所有的起始节点*/
        List<Long> startPoints = getStartPoints(nodes);
        /*找出所有的终止节点*/
        List<Long> endPoints = getEndPoints(nodes);
        for (Long startPoint : startPoints) {
            for (Long endPoint : endPoints) {
                findAllPath(nodes, startPoint, endPoint);
            }
        }
    }

    /**
     * 获取一个节点的所有父节点
     *
     * @param target
     * @param nodeList
     * @return
     */
    public static List<Long> getParentNodes(Long target, List<Node> nodeList) {
        List<Long> list = new ArrayList<>();
        nodeList.forEach(o -> {
            if (o.getTarget().equals(target)) {
                list.add(o.getSource());
            }
        });
        return list;
    }

    /**
     * 获取一个节点的所有子节点
     *
     * @param source
     * @param nodeList
     * @return
     */
    public static List<Long> getChildNodes(Long source, List<Node> nodeList) {
        List<Long> list = new ArrayList<>();
        nodeList.forEach(o -> {
            if (o.getSource().equals(source)) {
                list.add(o.getTarget());
            }
        });
        return list;
    }

    /**
     * 获取所有没有子节点的节点(终点)
     *
     * @param list
     * @return
     */
    public static List<Long> getEndPoints(List<Node> list) {
        Set<Long> parents = new HashSet<>();
        Set<Long> childs = new HashSet();
        list.forEach(o -> {
            childs.add(o.getTarget());
            parents.add(o.getSource());
        });
        List<Long> reduce = childs.stream().filter(item -> !parents.contains(item)).collect(Collectors.toList());
        return reduce;
    }

    /**
     * @param pointList
     * @param list
     * @return
     */
    public static List<Long> getNoLinkPoints(List<Long> pointList, List<Node> list) {
        Set<Long> set = new HashSet<>();
        list.forEach(o -> {
            set.add(o.getSource());
            set.add(o.getTarget());
        });
        List<Long> reduce = pointList.stream().filter(item -> !set.contains(item)).collect(Collectors.toList());
        return reduce;
    }

    /**
     * 获取所有没有父节点的节点(起点)
     *
     * @param list
     * @return
     */
    public static List<Long> getStartPoints(List<Node> list) {
        Set<Long> parentPoint = new HashSet<>();
        Set<Long> childsPoint = new HashSet();
        list.forEach(o -> {
            parentPoint.add(o.getSource());
            childsPoint.add(o.getTarget());
        });
        List<Long> reduce = parentPoint.stream().filter(item -> !childsPoint.contains(item)).collect(Collectors.toList());
        return reduce;
    }

    private void addPathList(List<Long> path) {
        this.pathList.add(path);
    }

    private void addCycleList(List<Long> path) {
        this.cycleList.add(path);
    }

    public List<List<Long>> getCycleList() {
        return new ArrayList<>(cycleList);
    }

    public List<List<Long>> getPathList() {
        /*去重*/
        return new ArrayList<>(pathList);
    }

    /**
     * @param nodeList
     * @param source   当前节点
     */
    private void findAllPath(List<Node> nodeList, Long source, Long target) {
        if (nodeList.size() > 0) {

            if (nowPath.contains(source)) {
                nowPath.add(source);
                addCycleList(new ArrayList<>(nowPath));
                nowPath.remove(nowPath.size() - 1);
                nowPath.remove(nowPath.size() - 1);
                return;
            }
            for (int i = 0; i < nodeList.size(); i++) {
                Node node = nodeList.get(i);
                if (node.getSource().equals(source)) {
                    nowPath.add(node.getSource());
                    if (node.getTarget().equals(target)) {
                        nowPath.add(node.getTarget());
                        addPathList(new ArrayList<>(nowPath));
                        /*因为添加了终点路径,所以要返回两次*/
                        nowPath.remove(nowPath.size() - 1);
                        nowPath.remove(nowPath.size() - 1);
                        /*已经找到路径,返回上层找其他路径*/
                        continue;
                    }
                    findAllPath(nodeList, node.getTarget(), target);
                }
            }
            /*如果找不到下个节点,返回上层*/
            if (nowPath.size() > 0) {
                nowPath.remove(nowPath.size() - 1);
            }
        }

    }


}
